The traffic data is constantly changing, an increase in the number of vehicles traveling in the congested transportation networks is stimulating such change. Accordingly, traffic data is being collected at an unprecedented scale to procure accurate information pertaining to traffic conditions. Needless to mention, location inaccuracies are unacceptable while assisting users in making an informed decision regarding their travel. Since, the navigation database needs to be updated instantaneously to reflect the changes in traffic conditions, service providers are collecting voluminous traffic data in real-time. However, it is inefficient to store complete time series traffic data for each road segments as it results in huge navigation database. One of the key performance indicators regarding the updatability of the underlying navigation database is for the update package to be as small as possible.